package A爆炸集;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class No827最大人工岛 {

    /**
     * 在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。
     * 进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
     *
     * 示例 1:
     * 输入: [[1, 0], [0, 1]]
     * 输出: 3
     * 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
     * 示例 2:
     * 输入: [[1, 1], [1, 0]]
     * 输出: 4
     * 解释: 将一格0变成1，岛屿的面积扩大为 4。
     * 示例 3:
     * 输入: [[1, 1], [1, 1]]
     * 输出: 4
     * 解释: 没有0可以让我们变成1，面积依然为 4。
     */

    private int[][] arr;
    private int allLength;
    private int itemLength;
    //上 右 下 左
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};
    private boolean[][] flag;

    /**
     * 对于此题呆瓜解法是依次每个位置为1,然后dfs计算最大岛屿,这样N^4,不好,下面的方法才好
     * 我们先计算出每个岛屿,然后就会知晓每个岛屿是多少块,然后每个块的值改为[多少块]的值,
     * 然后再依次遍历所有块,只遍历0的,return其上下左右加起来最大的数
     */
    public int largestIsland(int[][] grid) {
        this.allLength=grid.length;
        this.itemLength=grid[0].length;
        this.arr=grid;
        this.flag=new boolean[allLength][itemLength];
        //需要以1开头,因为0是水
        int index=1;
        int maxCount=0;
        boolean isWater=false;
        Deque<Integer> path=new ArrayDeque<>();
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(arr[i][j]==1&&!flag[i][j]){
                    //陆地&&未探索
                    int count = dfs(i, j, 0, path);
                    maxCount=Math.max(count,maxCount);
                    while (!path.isEmpty()){
                        Integer sum = path.removeFirst();
                        int x=sum/itemLength;
                        int y=sum%itemLength;
                        arr[x][y]=index;
                    }
                    //编号:块数
                    map.put(index,count);
                    index++;
                }
            }
        }
        //开始遍历0
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(arr[i][j]==0){
                    isWater=true;
                    /**
                     * 一个岛把上下左右都连通时的情况没有考虑到!
                     */
                    //每个边都要试一试其他边
                    for (int k = 0; k < 3; k++) {
                        int newX=i+around[k][0];
                        int newY=j+around[k][1];
                        if(verifyEdge(newX,newY)&&arr[newX][newY]!=0) {
                            //验证&&一边不可为水
                            int index1 = arr[newX][newY];
                            //一个边和其他边都比较一遍
                            int thisCount=map.get(index1);
                            for (int l = k + 1; l < 4; l++) {
                                int newX2 = i + around[l][0];
                                int newY2 = j + around[l][1];
                                /**
                                 * 当前困难点:
                                 * 1.两个连通的岛(值一样),合并一起
                                 * 2.值一样,也有可能是分开的
                                 * 所以在开始给岛屿赋值时,不可直接赋予整体块数,应该赋予编号Map对应块数
                                 */
                                if(verifyEdge(newX2,newY2)&&arr[newX2][newY2]!=0&&
                                        arr[newX][newY]!=arr[newX2][newY2]) {
                                    //2坐标通过&&两边不为同一组
                                    int index2 = arr[newX2][newY2];
                                    thisCount +=  + map.get(index2);
                                    maxCount=Math.max(maxCount,thisCount);
                                }else{
                                    maxCount=Math.max(maxCount,thisCount);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }

        return maxCount+(isWater?1:0);
    }

    private int dfs(int startX,int startY,int count,Deque<Integer> path){
        flag[startX][startY]=true;
        path.addLast(startX*itemLength+startY);
        for (int i = 0; i < 4; i++) {
            int newX=startX+around[i][0];
            int newY=startY+around[i][1];
            if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1
                    &&arr[newX][newY]==1&&!flag[newX][newY]){
                count=dfs(newX,newY,count,path);
            }
        }
        return count+1;
    }

    private boolean verifyEdge(int x,int y){
        return x>=0&&x<=allLength-1&&y>=0&&y<=itemLength-1;
    }

    public static void main(String[] args) {
        No827最大人工岛 n=new No827最大人工岛();
        int[][] arr=
                {
                {0,0,0,0,0,0,0},
                {0,1,1,1,1,0,0},
                {0,1,0,0,1,0,0},
                {1,0,1,0,1,0,0},
                {0,1,0,0,1,0,0},
                {0,1,0,0,1,0,0},
                {0,1,1,1,1,0,0}
                };
        int i = n.largestIsland(arr);
        System.out.println(i);
    }

}
